package 链表和树.链表;
//Java：回文链表
public class PalindromeLinkedList{
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//    public class ListNode {
//        int val;
//        ListNode next;
//        ListNode() {}
//        ListNode(int val) { this.val = val; }
//        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//    }
class Solution {
    public boolean isPalindrome(ListNode head) {
        //使用到链表的中间节点
        ListNode mid = middle(head);
        //翻转链表
        ListNode head2 = reverseNode(mid);

        //正式步骤判断回文
        while (head2!= null){
            if(head.val != head2.val){
                return false;
            }
            head = head.next;
            head2 = head2.next;
        }
        return true;
    }

    private ListNode  middle(ListNode head) {
        ListNode fast = head;
        ListNode slow =head;
        while(fast!=null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;

    }
    private ListNode reverseNode(ListNode cur){
        ListNode pre = null;
        while(cur != null){
            ListNode nxt= cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}